# encoding=utf-8
import time
'''
[7,5,3,6,44,22,99,11]
[3,5,7,6,44,22,99,11]  第一次
[3,5,7,6,44,22,99,11]  第二次
[3,5,6,7,44,22,99,11]  第三次
[3,5,6,7,44,22,99,11]  第四次
[3,5,6,7,11,22,99,44]  第五次
[3,5,6,7,11,22,99,44]  第六次
[3,5,6,7,11,22,44,99]  第七次
'''

#从列表中选择最大的元素放到最后一个位置
def select_sort(list):
    start_time=time.time()
    n = len(list)
    for i in range(n-1): #O n-1  O(n)
        #剩余列表中最小值的索引
        min_index = i
        for j in range(i+1,n):  #n-1 n-2 n-3  O(n)
            if list[min_index]>list[j]:
                min_index = j
        if min_index!=i:
            list[i],list[min_index]=list[min_index],list[i]
    end_time=time.time()
    print("选择排序执行时间：",end_time-start_time)
list = [7,5,3,6,44,22,99,11]
print("原数组:",list)
select_sort(list)
print("排序后数组：",list)

'''
最坏时间复杂度：O(n^2)
最优时间复杂度：O(n^2)
稳定性：不稳定(考虑升序每次选择最大的情况)
'''
